package org.usmile.algorithms.leetcode.hard;

import java.util.*;

/**
 * 642. 设计搜索自动补全系统
 *
 * 为搜索引擎设计一个搜索自动补全系统。用户会输入一条语句（最少包含一个字母，以特殊字符 '#' 结尾）。
 *
 * 给定一个字符串数组 sentences 和一个整数数组 times ，长度都为 n ，其中 sentences[i] 是之前输入的句子， times[i] 是该句子输入的相应次数。对于除 ‘#’ 以外的每个输入字符，返回前 3 个历史热门句子，这些句子的前缀与已经输入的句子的部分相同。
 *
 * 下面是详细规则：
 *
 * 一条句子的热度定义为历史上用户输入这个句子的总次数。
 * 返回前 3 的句子需要按照热度从高到低排序（第一个是最热门的）。如果有多条热度相同的句子，请按照 ASCII 码的顺序输出（ASCII 码越小排名越前）。
 * 如果满足条件的句子个数少于 3 ，将它们全部输出。
 * 如果输入了特殊字符，意味着句子结束了，请返回一个空集合。
 * 实现 AutocompleteSystem 类：
 *
 * AutocompleteSystem(String[] sentences, int[] times): 使用数组sentences 和 times 对对象进行初始化。
 * List<String> input(char c) 表示用户输入了字符 c 。
 * 如果 c == '#' ，则返回空数组 [] ，并将输入的语句存储在系统中。
 * 返回前 3 个历史热门句子，这些句子的前缀与已经输入的句子的部分相同。如果少于 3 个匹配项，则全部返回。
 *
 *
 * 示例 1：
 *
 * 输入
 * ["AutocompleteSystem", "input", "input", "input", "input"]
 * [[["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]], ["i"], [" "], ["a"], ["#"]]
 * 输出
 * [null, ["i love you", "island", "i love leetcode"], ["i love you", "i love leetcode"], [], []]
 *
 * 解释
 * AutocompleteSystem obj = new AutocompleteSystem(["i love you", "island", "iroman", "i love leetcode"], [5, 3, 2, 2]);
 * obj.input("i"); // return ["i love you", "island", "i love leetcode"]. There are four sentences that have prefix "i". Among them, "ironman" and "i love leetcode" have same hot degree. Since ' ' has ASCII code 32 and 'r' has ASCII code 114, "i love leetcode" should be in front of "ironman". Also we only need to output top 3 hot sentences, so "ironman" will be ignored.
 * obj.input(" "); // return ["i love you", "i love leetcode"]. There are only two sentences that have prefix "i ".
 * obj.input("a"); // return []. There are no sentences that have prefix "i a".
 * obj.input("#"); // return []. The user finished the input, the sentence "i a" should be saved as a historical sentence in system. And the following input will be counted as a new search.
 *
 * 提示:
 *
 * n == sentences.length
 * n == times.length
 * 1 <= n <= 100
 * 1 <= sentences[i].length <= 100
 * 1 <= times[i] <= 50
 * c 是小写英文字母， '#', 或空格 ' '
 * 每个被测试的句子将是一个以字符 '#' 结尾的字符 c 序列。
 * 每个被测试的句子的长度范围为 [1,200]
 * 每个输入句子中的单词用单个空格隔开。
 * input 最多被调用 5000 次
 */
public class _0642 {
}

class _0642_Solution {
    private static class AutocompleteSystem {

        private static class Sentence {
            String content;
            int time;

            Sentence(String content, int time) {
                this.content = content;
                this.time = time;
            }
        }

        private static class TrieNode {
            Map<Character, TrieNode> children = new HashMap<>();
            // times == 0 说明，这个节点不是字符串的结尾节点
            // times > 0 说明是结尾字符节点
            int times = 0;
        }

        private final TrieNode root;
        // 记录用户当前的输入
        private String currSentence = "";

        public AutocompleteSystem(String[] sentences, int[] times) {
            root = new TrieNode();
            // 构建前缀树
            for (int i = 0; i < sentences.length; i++) {
                insert(sentences[i], times[i]);
            }
        }

        public void insert(String s, int times) {
            TrieNode curr = root;
            for (char c : s.toCharArray()) {
                if (!curr.children.containsKey(c)) {
                    curr.children.put(c, new TrieNode());
                }
                curr = curr.children.get(c);
            }
            curr.times += times;
        }

        public List<String> input(char c) {
            List<String> res = new ArrayList<>();
            if (c == '#') { // 用户输入完成一个句子
                // 更新这个句子总的被搜索次数
                insert(currSentence, 1);
                // 清除用户当前输入
                currSentence = "";
            } else {
                // 1. 将当前输入字符拼接到当前句子
                currSentence += c;

                // 2. 找到所有以当前输入字符串开头的句子
                // 从字典树中找到包含 currSentence 为前缀的所有句子
                List<Sentence> list = lookup(currSentence);

                // 3. 拿到被搜索次数排名前 3 的句子
                list.sort((o1, o2) -> o1.time == o2.time ? o1.content.compareTo(o2.content) : o2.time - o1.time);
                for (int i = 0; i < Math.min(3, list.size()); i++) {
                    res.add(list.get(i).content);
                }
            }
            return res;
        }

        // 从当前前缀树中搜索以 s 开头的所有的句子
        public List<Sentence> lookup(String s) {
            List<Sentence> list = new ArrayList<>();

            // 1. 找到前缀
            TrieNode curr = root;
            for (char c : s.toCharArray()) {
                if (!curr.children.containsKey(c)) {
                    return list;
                }
                curr = curr.children.get(c);
            }

            // 2. 找到以前缀结尾的所有的字符串
            dfs(curr, s, list);

            return list;
        }

        private void dfs(TrieNode curr, String s, List<Sentence> list) {
            if (curr.times > 0) {
                list.add(new Sentence(s, curr.times));
            }

            for (char c : curr.children.keySet()) {
                dfs(curr.children.get(c), s + c, list);
            }
        }
    }
}